﻿
namespace Leetcode.N0208;
public class Trie
{

    private string value;
    private Trie[] children;

    public Trie()
    {
    }

    public void Insert(string word)
    {
        this.Insert(word, 0);
    }

    private void Insert(string word, int index)
    {
        if (this.children == null)
        {
            this.children = new Trie[26];
        }

        var node = this.children[word[index] - 'a'];
        if (node == null)
        {
            node = new Trie();
            this.children[word[index] - 'a'] = node;
        }

        if (index == word.Length - 1)
        {
            node.value = word;
        }
        else
        {
            node.Insert(word, index + 1);
        }
    }
    public bool Search(string word)
    {
        return this.Search(word, 0);
    }

    private bool Search(string word, int index)
    {
        if (this.children == null)
        {
            return false;
        }
        var node = this.children[word[index] - 'a'];
        if (node == null)
        {
            return false;
        }

        if (index == word.Length - 1)
        {
            return node.value != null;
        }
        else
        {
            return node.Search(word, index + 1);
        }
    }

    public bool StartsWith(string prefix)
    {
        return this.StartsWith(prefix, 0);
    }

    private bool StartsWith(string prefix, int index)
    {
        if (this.children == null)
        {
            return false;
        }

        var node = this.children[prefix[index] - 'a'];
        if (node == null)
        {
            return false;
        }

        if (index == prefix.Length - 1)
        {
            return true;
        }

        return node.StartsWith(prefix, index + 1);
    }
}
